The present invention relates generally to the field of computer memory analysis, and more particularly to de-allocation of memory portions suitable for putting into a “freed” status.
“Reference counting” is a technique of storing the number of references (also called, pointers, or handles) to a resource, such as an object, a block of memory, a portion of disk space or other resource. Some garbage collection algorithms use forms of reference counting. Generally speaking, reference counting uses a set of numerical variables, called “reference counts,” to de-allocate objects (for example, memory blocks) based upon whether the object associated with a given reference count is no longer being referenced by any referencing entities (for example, threads of access to data). In the context of a collection algorithm, reference counting tracks, for each object, a count of the number of references to it held by other referencing entities. If an object's reference count reaches zero, the object is no longer being accessed (typically meaning that the object can be freed for other uses, de-allocated and/or destroyed).
As mentioned above, one conventional way to track when a memory block can be freed (that is, de-allocated) is via reference counting. When a thread of access to data (note, throughout this document, unless otherwise explicitly noted, “threads” will refer to threads of access to data, rather than threads of execution of instructions) has a need to access a given memory block, that thread increments the reference count associated with the given memory. The thread subsequently decrements the associated reference count when the thread will no longer require access to the given memory block. Typically, this incrementing and decrementing of reference counts is visible to all threads and is “atomic.” On a modern CPU (central processing unit), such globally-visible atomic changes to the reference count will require memory barriers (to ensure the change is visible to other threads) and have associated, non-negligible cost for many use cases.